package leetcode.N101_N200;

import leetcode.comm.ListNode;


/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/11/20 2:36 下午
 */
public class N147 {

    public static void main(String[] args) {
        N147 a = new N147();
        ListNode generate = ListNode.generate(4, 2, 1, 3);
        System.out.println(a.insertionSortList(generate));
    }

    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 已经排序的表头
        ListNode start = head;
        // 已经排序的表尾
        ListNode end = head;
        // 当前需要判断的节点
        ListNode currentNode = end.next;

        while (currentNode != null) {
            if (end.val <= currentNode.val) {
                // 当前节点大于前面所有的数 则调到下一个节点
                end = currentNode;
            } else {
                // 进入子序列
                // 既然要往前插入，所以end还是原来的end 但是需要连接current的next
                // 这个操作相当于把currentNode从原本的链表里面删除
                end.next = currentNode.next;
                // 将当前节点插入到有序列表中  返回新的队头
                start = doInsert(start, currentNode);

            }
            // 下一个当前节点
            currentNode = end.next;
        }
        // 最终返回已经排序的表头
        return start;
    }

    private ListNode doInsert(ListNode start, ListNode currentNode) {
        if (currentNode.val <= start.val) {
            // 当前节点是最小节点
            currentNode.next = start;
            return currentNode;
        }
        // 遍历节点找到适合的位置插入当前节点
        ListNode lastNode = start;
        while (lastNode.next != null) {
            if (currentNode.val <= lastNode.next.val) {
                // 在lastNode后插入当前节点
                currentNode.next = lastNode.next;
                lastNode.next = currentNode;
                break;
            } else {
                lastNode = lastNode.next;
            }
        }
        return start;
    }

}
